<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
    "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<meta name="generator" content="AsciiDoc 8.3.4" />
<title><em>utlist</em>: linked list macros for C structures</title>
<link rel="stylesheet" href="./tdh.css" type="text/css" />
<link rel="stylesheet" href="./tdh-quirks.css" type="text/css" />
</head>
<body>
<div id="header">
<h1><em>utlist</em>: linked list macros for C structures</h1>
<span id="author">Troy D. Hanson</span><br />
<span id="email"><tt>&lt;<a href="mailto:thanson@users.sourceforge.net">thanson@users.sourceforge.net</a>&gt;</tt></span><br />
<span id="revision">version 1.0,</span>
May 2009
</div>
<div id="preamble">
<div class="sectionbody">
<a style="float: right; padding-right: 50px" href="http://sourceforge.net/projects/uthash"><img style="border: 0" src="http://sflogo.sourceforge.net/sflogo.php?group_id=163879&amp;type=13" width="120" height="30" alt="uthash at SourceForge.net" /></a>
  <div id="topnav" style="font-size: 9pt; font-family: sans-serif;">
  <a style="padding: 8px;" href="index.html">uthash home</a>
  >>  utlist macros
  </div>
</div>
</div>
<h2 id="_introduction">Introduction</h2>
<div class="sectionbody">
<div id="toc"></div>
<script>
window.onload=generate_TOC

/* Author: Mihai Bazon, September 2002
 * <a href="http://students.infoiasi.ro/~mishoo">http://students.infoiasi.ro/~mishoo</a>
 *
 * Table Of Content generator
 * Version: 0.4
 *
 * Feel free to use this script under the terms of the GNU General Public
 * License, as long as you do not remove or alter this notice.
 */

 /* modified by Troy D. Hanson, September 2006. License: GPL */

function H_getText(el) {
  var text = "";
  for (var i = el.firstChild; i != null; i = i.nextSibling) {
    if (i.nodeType == 3 /* Node.TEXT_NODE, IE doesn't speak constants */)
      text += i.data;
    else if (i.firstChild != null)
      text += H_getText(i);
  }
  return text;
}

function TOC_EL(el, text, level) {
  this.element = el;
  this.text = text;
  this.level = level;
}

function getHeadlines(el) {
  var l = new Array;
  var rx = /[hH]([2-3])/;
  // internal recursive function that scans the DOM tree
  var rec = function (el) {
    for (var i = el.firstChild; i != null; i = i.nextSibling) {
      if (i.nodeType == 1 /* Node.ELEMENT_NODE */) {
        if (rx.exec(i.tagName))
          l[l.length] = new TOC_EL(i, H_getText(i), parseInt(RegExp.$1));
        rec(i);
      }
    }
  }
  rec(el);
  return l;
}

function generate_TOC() {
  var parent = document.getElementById("toc");
  var toc_hdr = document.createElement("div");
  var toc_hdr_txt = document.createTextNode("CONTENTS");
  toc_hdr.appendChild(toc_hdr_txt);
  /* toc_hdr.setAttribute("id","hdr"); */
  toc_hdr.id = "hdr";
  parent.appendChild(toc_hdr);
  var hs = getHeadlines(document.getElementsByTagName("body")[0]);
  for (var i = 0; i < hs.length; ++i) {
    var hi = hs[i];
    var d = document.createElement("div");
    if (hi.element.id == "") hi.element.id = "gen" + i;
    var a = document.createElement("a");
    a.href = "#" + hi.element.id;
    a.appendChild(document.createTextNode(hi.text));
    d.appendChild(a);
    d.className = "level" + hi.level;
    parent.appendChild(d);
    /*
    if (hi.level == 3) {
        var dvtop = document.createElement("div");
        dvtop.className = "toplink";
        dvtop.appendChild(document.createTextNode("^top^"));
        dvtop.onclick=function(){scrollTo(0,0);};
        hi.element.appendChild(dvtop);
    }
    */
  }
}
</script>
<div class="paragraph"><p>A set of general-purpose <em>linked list</em> macros for C structures are included with
uthash in <tt>src/utlist.h</tt>.  To use these macros in your own C program, just
copy <tt>utlist.h</tt> into your source directory and use it in your programs.</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>#include "utlist.h"</tt></pre>
</div></div>
<div class="paragraph"><p>These macros support the basic linked list operations: adding and deleting
elements, sorting them and iterating over them.</p></div>
<h3 id="_download">Download</h3><div style="clear:left"></div>
<div class="paragraph"><p>To download the <tt>utlist.h</tt> header file, follow the link to download on the
<a href="http://uthash.sourceforge.net">uthash home page</a>. Untar the package, and
look in the <tt>src/</tt> directory for <tt>utlist.h</tt>.</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>tar -xjf uthash-1.6.tar.bz2
cd uthash-1.6/src
cp utlist.h &lt;destdir&gt;</tt></pre>
</div></div>
<h3 id="_bsd_licensed">BSD licensed</h3><div style="clear:left"></div>
<div class="paragraph"><p>This software is made available under the
<a href="license.html">revised BSD license</a>.
It is free and open source.</p></div>
<h3 id="_platforms">Platforms</h3><div style="clear:left"></div>
<div class="paragraph"><p>The <em>utlist</em> macros have been tested on:</p></div>
<div class="ulist"><ul>
<li>
<p>
Linux,
</p>
</li>
<li>
<p>
Mac OS X, and
</p>
</li>
<li>
<p>
Windows, using Cygwin or MinGW.
</p>
</li>
</ul></div>
</div>
<h2 id="_using_utlist">Using utlist</h2>
<div class="sectionbody">
<h3 id="_types_of_lists">Types of lists</h3><div style="clear:left"></div>
<div class="paragraph"><p>Three types of linked lists are supported:</p></div>
<div class="ulist"><ul>
<li>
<p>
<strong>singly-linked</strong> lists,
</p>
</li>
<li>
<p>
<strong>doubly-linked</strong> lists, and
</p>
</li>
<li>
<p>
<strong>circular, doubly-linked</strong> lists
</p>
</li>
</ul></div>
<h4 id="_efficiency">Efficiency</h4>
<div class="paragraph"><p>For all types of lists, prepending elements and deleting elements are
constant-time operations. Appending to a singly-linked list is an <em>O(n)</em>
operation but appending to a doubly-linked list is constant time using these
macros.  (This is because, in the utlist implementation of the doubly-linked
list, the head element&#8217;s <tt>prev</tt> member points back to the list tail, even when
the list is non-circular). Sorting is an <em>O(n log(n))</em> operation.</p></div>
<h3 id="_list_elements">List elements</h3><div style="clear:left"></div>
<div class="paragraph"><p>You can use any structure with these macros, as long as the structure
contains a <tt>next</tt> pointer. If you want to make a doubly-linked list,
the element also needs to have a <tt>prev</tt> pointer.</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>typedef struct {
    char *name;
    struct element *prev; /* needed for a doubly-linked list only */
    struct element *next; /* needed for singly- or doubly-linked lists */
} element;</tt></pre>
</div></div>
<div class="paragraph"><p>You can name your structure anything. In the example above it is called <tt>element</tt>.
Within a particular list, all elements must be of the same type.</p></div>
<h3 id="_list_head">List head</h3><div style="clear:left"></div>
<div class="paragraph"><p>The list head is simply a pointer to your element structure. You can name it
anything. <strong>It must be initialized to <tt>NULL</tt></strong>.</p></div>
<div class="literalblock">
<div class="content">
<pre><tt>element *head = NULL;</tt></pre>
</div></div>
<h3 id="_list_operations">List operations</h3><div style="clear:left"></div>
<div class="paragraph"><p>The lists support inserting or deleting elements, sorting the elements and
iterating over them.</p></div>
<div class="tableblock">
<table rules="cols"
width="90%"
frame="border"
cellspacing="0" cellpadding="4">
<col width="33%" />
<col width="33%" />
<col width="33%" />
<thead valign="top">
<tr>
<th align="center">Singly-linked             </th>
<th align="center"> Doubly-linked              </th>
<th align="center"> Circular, doubly-linked</th>
</tr>
</thead>
<tbody valign="top">
<tr>
<td align="center"><p class="table"><tt>LL_PREPEND(head,add);</tt></p></td>
<td align="center"><p class="table"><tt>DL_PREPEND(head,add);</tt></p></td>
<td align="center"><p class="table"><tt>CDL_PREPEND(head,add;</tt></p></td>
</tr>
<tr>
<td align="center"><p class="table"><tt>LL_APPEND(head,add);</tt></p></td>
<td align="center"><p class="table"><tt>DL_APPEND(head,add);</tt></p></td>
<td align="center"><p class="table"><tt></tt></p></td>
</tr>
<tr>
<td align="center"><p class="table"><tt>LL_DELETE(head,del);</tt></p></td>
<td align="center"><p class="table"><tt>DL_DELETE(head,del);</tt></p></td>
<td align="center"><p class="table"><tt>CDL_DELETE(head,del);</tt></p></td>
</tr>
<tr>
<td align="center"><p class="table"><tt>LL_SORT(head,cmp);</tt></p></td>
<td align="center"><p class="table"><tt>DL_SORT(head,cmp);</tt></p></td>
<td align="center"><p class="table"><tt>CDL_SORT(head,cmp);</tt></p></td>
</tr>
<tr>
<td align="center"><p class="table"><tt>LL_FOREACH(head,elt) {&#8230;}</tt></p></td>
<td align="center"><p class="table"><tt>DL_FOREACH(head,elt) {&#8230;}</tt></p></td>
<td align="center"><p class="table"><tt>CDL_FOREACH(head,elt) {&#8230;}</tt></p></td>
</tr>
</tbody>
</table>
</div>
<div class="paragraph"><p><em>Prepend</em> means to insert an element in front of the existing list head (if any),
changing the list head to the new element. <em>Append</em> means to add an element at the
end of the list, so it becomes the new tail element.</p></div>
<div class="paragraph"><p>The <em>sort</em> operation never moves the elements in memory; rather it only adjusts
the list order by altering the <tt>prev</tt> and <tt>next</tt> pointers in each element. Also
the sort operation can change the list head to point to a new element.</p></div>
<div class="paragraph"><p>The <em>foreach</em> operation is for easy iteration over the list from the head to the
tail. A usage example is shown below. You can of course just use the <tt>prev</tt> and
<tt>next</tt> pointers directly instead of using the <em>foreach</em> macros.</p></div>
<div class="paragraph"><p>The parameters shown in the table above are explained here:</p></div>
<div class="dlist"><dl>
<dt class="hdlist1">
head
</dt>
<dd>
<p>
  The list head (a pointer to your list element structure).
</p>
</dd>
<dt class="hdlist1">
add
</dt>
<dd>
<p>
  A pointer to the list element structure you are adding to the list.
</p>
</dd>
<dt class="hdlist1">
del
</dt>
<dd>
<p>
  A pointer to the list element structure you are deleting from the list.
</p>
</dd>
<dt class="hdlist1">
elt
</dt>
<dd>
<p>
  A pointer that will be assigned to each list element in succession (see
  example).
</p>
</dd>
<dt class="hdlist1">
cmp
</dt>
<dd>
<p>
  pointer to comparison function which accepts two arguments-- these are
  pointers to two element structures to be compared. The comparison function
  must return an <tt>int</tt> that is negative, zero, or positive, which specifies
  whether the first item should sort before, equal to, or after the second item,
  respectively. (In other words, the same convention that is used by <tt>strcmp</tt>).
</p>
</dd>
</dl></div>
<h3 id="_example">Example</h3><div style="clear:left"></div>
<div class="paragraph"><p>This example program reads names from a text file (one name per line), and
appends each name to a doubly-linked list. Then it sorts and prints them.</p></div>
<div class="listingblock">
<div class="title">A doubly-linked list</div>
<div class="content">
<pre><tt>#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;
#include "utlist.h"

#define BUFLEN 20

typedef struct el {
    char bname[BUFLEN];
    struct el *next, *prev;
} el;

int namecmp(el *a, el *b) {
    return strcmp(a-&gt;bname,b-&gt;bname);
}

el *head = NULL; /* important- initialize to NULL! */

int main(int argc, char *argv[]) {
    el *name, *tmp;

    char linebuf[BUFLEN];
    FILE *file;

    if ( (file = fopen( "test11.dat", "r" )) == NULL ) {
        perror("can't open: ");
        exit(-1);
    }

    while (fgets(linebuf,BUFLEN,file) != NULL) {
        if ( (name = (el*)malloc(sizeof(el))) == NULL) exit(-1);
        strncpy(name-&gt;bname,linebuf,BUFLEN);
        DL_APPEND(head, name);
    }
    DL_SORT(head, namecmp);
    DL_FOREACH(head,tmp) printf("%s", tmp-&gt;bname);

    fclose(file);

    return 0;
}</tt></pre>
</div></div>
</div>
<div id="footer">
<div id="footer-text">
Version 1.0<br />
Last updated 2009-05-08 23:34:23 EDT
</div>
</div>
</body>
</html>
